package com.adamjwh.pratice.offer;

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 */
public class JudgePostOrder {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null || sequence.length==0) {
            return false;
        }

        return isPost(sequence, 0, sequence.length-1);
    }

    //对于一个二叉树的后序遍历序列来说，最后一个数一定是根节点，然后前面的数中，从最开始到第一个大于根节点的数都是左子树中的数，而后面到倒数第二个数应该都是大于根节点的，是右子树，如果后面的数中有小于根节点的，那么说明这个序列不是二叉搜索树的后序遍历序列
    private boolean isPost(int[] arr, int start, int end) {
        if(start > end) {
            return true;
        }

        int index = end - 1;
        while(index>start && arr[index]>arr[end]) {
            index --;
        }

        for(int i=start; i<index; i++) {
            if(arr[i] > arr[end]) {
                return false;
            }
        }

        return isPost(arr, start, index) && isPost(arr, index+1, end-1);    //递归左和右
    }
}
